package com.laotang.第_16_章_字典树.力扣_211_添加与搜索单词_数据结构设计;

public class _211_add_and_search_words_data_structure {
}

class WordDictionary {

    private class Node {
        Node[] children;
        boolean isWord;

        Node() {
            children = new Node[26];
            isWord = false;
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        Node curr = root;
        for (Character c : word.toCharArray()) {
            if (curr.children[c - 'a'] == null) {
                curr.children[c - 'a'] = new Node();
            }
            curr = curr.children[c - 'a'];
        }
        curr.isWord = true;
    }

    /** Returns if the word is in the data structure.
     A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(Node node, String word, int index) {
        if (index == word.length()) return node.isWord;

        Character c = word.charAt(index);
        if (c != '.') {
            if (node.children[c - 'a'] == null) return false;
            return dfs(node.children[c - 'a'], word, index + 1);
        } else {
            for (Node child : node.children) {
                if (child != null && dfs(child, word, index + 1)) return true;
            }
            return false;
        }
    }
}

